package sort;

/**
 * 三色数组排序
 * @author Administrator
 *
 */
public class ThreeColorSort {

	public static void main(String[] args) {
		int[] a = { 0, 1, 2, 1, 1, 2 };
		sort(a, 6);
		for (int i : a) {
			System.out.print(i + " ");
		}
	}

	public static void sort(int[] a, int len) {
		int left = 0;
		int right = len - 1;

		for (int i = 0; i < len; i++) {
			if (i > right) {
				break;
			}

			if (i > left && a[i] == 0) {
				swap(a, i--, left++);
			}

			if (right > i && a[i] == 2) {
				swap(a, i--, right--);
			}
		}
	}

	public static void swap(int[] arr, int a, int b) {
		int tmp = arr[a];
		arr[a] = arr[b];
		arr[b] = tmp;
	}
}
